Okay, you can hear me, good.

Good morning on this dreary November day.

All the more respect that you made it here.

So, we are talking about what is called general problems or search problems.

Problems which we can formulate in terms of world states, actions, and initial states and goal states.

Goal states show us we're in the setting of a goal-based agent.

Goal-based agent means rather than the agent setting its own goals, we do that next semester,

the agent designer premeditates and specifies the goal.

And we've been looking at informed search strategies.

Informed search strategies are things that, in addition to the problem formulation,

are given a so-called heuristic, which is a function that basically evaluates nodes by their desirability.

We've looked at the first idea of how to make use of this, which was greedy search,

and we've convinced ourselves that while this is a good idea, and sometimes it even works,

we can and should do better.

And to that end, we've introduced something called A-star search.

A-star search being a variant of greedy search, where instead of using the raw heuristic,

we add an annoyance term that keeps us from doing the same things again and again.

The chicken problem.

So that's what A-star search is.

Instead of using H alone, we use the function f, which is g,

g being the cost we've already spent on the path in the tree, plus the evaluation.

We've convinced ourselves that this is an optimal search strategy.

We looked at examples, and basically we looked at these maze examples,

where it shows us even though greedy search performs better time-wise,

sometimes A-star is optimal, and not that much worse.

So we see the greedy search numbers, which guide the search pretty well,

in the bad case, they also guide it down the garden paths.

Whereas A-star search has bigger numbers and bigger regions of indecisions,

also here is one, it actually precludes things from going down the garden path.

And of course, A-star search is not quite as good as if we have,

with the Manhattan distance, is not quite as good as having A-star search for the perfect heuristic,

but still good.

Okay, we talked about the properties.

A-star is complete, has exponential time complexity,

but it's not exponential in the depth of the search tree,

but it's exponential in something better.

It's really the area between the heuristic and the perfect heuristic.

Kind of the relative heuristic error, that's what it is, exponential in.

Which means rather than being controlled by the search problem,

it's controlled by the quality of the heuristic,

which is actually a very good thing.

Because we have it, the Asian designer who supplies the heuristic actually has it under control.

Okay, and the last thing we kind of looked at, started looking at,

was finding the art of finding good heuristics.

And it is an art.

I'm going to give you the start of a recipe, but that doesn't always work.

Or actually requires some kind of creativity on the part of the Asian designer.

So the first thing we do is we look at an example.

We look at the nine puzzle.

And so we have a start state.